package map_and_set;

import java.util.*;

public class TopKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        // map 用来统计出现的单词及其出现的次数
        HashMap<String,Integer> map = new HashMap<>();
        // 1. 统计每个单词出现的次数
        for (String word: words) {
            if(map.get(word) == null){
                map.put(word,1);
            }else{
                int val = map.get(word);
                map.put(word,val + 1);
            }
        }
        // 2. 找前K个出现次数最多的 建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        // 3. 遍历 map
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0){
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if(top.getKey().compareTo(entry.getKey()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        ArrayList<String> list = new ArrayList<>();
        for(int i = 0;i < k;i++){
            Map.Entry<String,Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
